package 剑指offer;

/**
 * @author zhangmin
 * @create 2021-11-18 9:47
 *
 * 动态规划
 */
public class day8_101_102_63 {
    /**===========================================================================================================================
     * 剑指 Offer 10- I. 斐波那契数列
     * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
     * F(0) = 0,   F(1) = 1
     * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.----递推表达式
     * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1
     *
     * 1、dp
     * 2、压缩空间：只和前两个元素有关
     * 3、快速矩阵幂运算
     * */
    public int fib1(int n) {
        final int MOD = 1000000007;
        if (n<2) return n;
        int[] f=new int[n+1];
        f[0]=0;f[1]=1;
        for (int i = 2; i < n+1; i++) {
            f[i]=(f[i-1]+f[i-2])%MOD;
        }
        return f[n];
    }
    public int fib(int n) {
        final int MOD = 1000000007;
        if (n<2) return n;
        int f1=0,f2=1,f=0;
        for (int i = 2; i < n+1; i++) {
            f=(f1+f2)%MOD;
            f1=f2;
            f2=f;
        }
        return f;
    }


    /**===========================================================================================================================
     * 剑指 Offer 10- II. 青蛙跳台阶问题
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
     * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
     * dp:dp[i]表示跳上i个台阶有多少种跳法，dp[i]=dp[i-1](跳一级到达i)+dp[i-2](跳两级到达i)
     * dp[0]=1,dp[1]=1;-----斐波那契堆
     * */
    public int numWays(int n) {
        final int MOD = 1000000007;
        if (n<2) return 1;
        int[] f=new int[n+1];
        f[0]=1;f[1]=1;
        for (int i = 2; i < n+1; i++) {
            f[i]=(f[i-1]+f[i-2])%MOD;
        }
        return f[n];
    }

    /**===========================================================================================================================
     * 剑指 Offer 63. 股票的最大利润
     * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
     * 1、dp:计算出每一天和前一天的价格差值，查找差值序列的最大子数组 dp[i]表示以i为结尾的最大子数组和：dp[i]=max{dp[i-1]+nums[i],nums[i]}
     * 2、dp:dp变成二维的 dp[i][0](第i天不持有股票的最大利益) = max(dp[i-1][0], dp[i-1][1] + prices[i])
     *                  dp[i][1](第i天持有股票的最大利益) = max(dp[i-1][1], -prices[i]（前一天不持有股票，在第i天买入，之前没有累计的利益）)
     * */
    public int maxProfit1(int[] prices) {
        int n=prices.length;
        if (n==0) return 0;
        int[] nums=new int[n];
        int[] dp=new int[n];
        nums[0]=0;dp[0]=0;
        int res=0;
        for (int i = 1; i < n; i++) {
            nums[i]=prices[i]-prices[i-1];
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            res=Math.max(dp[i],res);
        }
        return res;
    }
    public int maxProfit(int[] prices) {
        int n=prices.length;
        if (n==0) return 0;
        int[][] dp=new int[n][2];
        dp[0][0]=0;dp[0][1]=-prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
        }
        return dp[n-1][0];
    }
}
